#!/usr/bin/python



#este es el grafo de ejemplo que me genera la matris
# 0 -> 3
# 1 -> 3
# 2 -> 3
# 4 -> 3
# 2 - > 5  
adjacencyMatix = [	[0,0,0,1,0,0] , \
					[0,0,0,1,0,0] , \
					[0,0,0,1,0,0] , \
					[1,1,1,0,1,0] , \
					[0,0,0,1,0,0] , \
					[0,0,1,0,0,0] ]	

stations = [0]
def nodeIsConnected(node,parent=None):
	global adjacencyMatix
	
	if node in stations:
		return True

	for i in range(len(adjacencyMatix)):
		if i == node or i == parent:
			continue

		if adjacencyMatix[node][i] and nodeIsConnected(i,node):
			return True
		# if adjacencyMatix[i][node] && nodeIsConnected(node):
		# 	return True
	return False

#aca tengo los 2 nodos mas el peso del eje desordenados
axis = [(0,3,1),(1,3,2),(2,3,5),(2,5,2),(3,4,1)]
#ordeno
axisSorted = sorted(axis, key=lambda a: a[2] )
axisSorted.reverse()
for i in range(len(axis)):
	print "%d tiene estacion? -> %d, %d tiene estacion? -> %d"	 % (axisSorted[i][0],\
		nodeIsConnected(axisSorted[i][0]),\
		axisSorted[i][1],\
		nodeIsConnected(axisSorted[i][1]))

estacionesCant = 3
#para 1 sola estacion esto no se ejecuta
#en el loop parto de la premisa que siempre que saco un eje dejo
#2 componentes en la que de un lado hay una estacion 
#en el primer caso tiro la estacion en cualquier nodo 
#la primera no me importa
print axisSorted
for i in range(estacionesCant-1):
	ax = axisSorted[i]		
	#tomo el eje lo desconecto
	adjacencyMatix[ax[0]][ax[1]] = 0
	adjacencyMatix[ax[1]][ax[0]] = 0
	#la matriz hay que optimizarla
	if nodeIsConnected(ax[0]):
		stations.append(ax[1])
	else:
		stations.append(ax[0])

print stations
print adjacencyMatix